import java.io.File;
import java.io.PrintWriter;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;


public class Planificacion {
	
	public static double TAMANIO_CELDA = 300;
	
	private Celda[][][][] celdas;
	
	private Point inicialA;
	
	private Point finA;
	
	private Point inicialB;
	
	private Point finB;

	private ArrayList<Celda>[] esquinas;
	
	private ArrayList<Celda>[] lista;
	
	private char orientacionInicialA;
	
	private char orientacionFinalA;
	
	
	private char orientacionInicialB;
	
	private char orientacionFinalB;
	
	public void loadMap(File file)throws Exception{
		Scanner scan = new Scanner(file);
		
		//Se escanea AQI
		scan.next();
		int px = scan.nextInt();
		int py = scan.nextInt();
		scan.nextInt();
		inicialA = new Point(px,py);
		
		//Se escanea AQF
		scan.next();
		px = scan.nextInt();
		py = scan.nextInt();
		scan.nextInt();
		finA = new Point(px,py);
		
		//Se escanea BQI
		scan.next();
		px = scan.nextInt();
		py = scan.nextInt();
		scan.nextInt();
		inicialB = new Point(px,py);
		
		//Se escanea BQF
		scan.next();
		px = scan.nextInt();
		py = scan.nextInt();
		scan.nextInt();
		finB = new Point(px,py);
		
		int filas = scan.nextInt();
		int cols = scan.nextInt();
		System.out.println(filas+"-"+cols);
		celdas = new Celda[2][filas][cols][4];
		lista = new ArrayList[2];
		esquinas = new ArrayList[2];
		int fia = 0,cia = 0,ffa=0,cfa=0;
		int fib = 0,cib = 0,ffb=0,cfb=0;
		for (int i = 0; i < filas; i++) {
			for (int j = 0; j < cols; j++) {
				String s = scan.next();
				int p;
				char o = '-';
				if(s.equals("ooo")){
					p = Celda.PARED;
				}else if(s.equals("...")){
					p = Celda.VACIA;
				}else if(s.startsWith("AI")){ 
					p = Celda.INICIALA;
					o = s.charAt(2);
					
					orientacionInicialA = o;
					cia=j;
					fia=i;
				}else if(s.startsWith("AF")){
					p = Celda.FINALA;
					o = s.charAt(2);
					orientacionFinalA = o;
					cfa=j;
					ffa=i;
				}else if(s.startsWith("BI")){
					p = Celda.INICIALB;
					o = s.charAt(2);
					orientacionInicialB = o;
					cib=j;
					fib=i;
				}else{
					p = Celda.FINALB;
					o = s.charAt(2);
					orientacionFinalB = o;
					cfb=j;
					ffb=i;	
				}
				for (int k = 0; k < 4; k++) {					
					celdas[0][i][j][k] = new Celda(p,numToDir(k),i,j);
					celdas[1][i][j][k] = new Celda(p,numToDir(k),i,j);
				}
			}
		}
		
		generateMatrix(ffa,cfa,0,orientacionInicialA);
		
		findPath(fia,cia,ffa,cfa,orientacionInicialA,0);
		fixPoints(0);
		findPath(fia, cia, ffa, cfa,orientacionInicialA,0);
		planificacionTiempos(0, orientacionInicialA,orientacionFinalA);
		
		String name = file.getAbsolutePath().substring(0, file.getAbsolutePath().length()-4)+"-camino-A.txt";
		File destiny = new File(name);
		printResults(destiny,ffa,cfa,0);
		
		generateMatrix(ffb,cfb,1,orientacionInicialB);
		findPath(fib,cib,ffb,cfb,orientacionInicialB,1);
		fixPoints(1);
		findPath(fib, cib, ffb, cfb,orientacionInicialB,1);
		fixEncounters();
		//Al arreglar los encuentros, el costo del camino puede haber cambiado, por lo que es necesario reinicializar la matriz y calcular todo nuevamente
		for (int k = 0; k < celdas[1].length; k++) {
			for (int k2 = 0; k2 < celdas[1][0].length; k2++) {
				for (int l = 0; l < celdas[1][0][0].length; l++) {
					celdas[1][k][k2][l]=new Celda(celdas[1][k][k2][l].getEstado(),numToDir(l),k,k2);
				}
			}
		}
		
		generateMatrix(ffb,cfb,1,orientacionInicialB);
		findPath(fib, cib, ffb, cfb,orientacionInicialB,1);
		
		name = file.getAbsolutePath().substring(0, file.getAbsolutePath().length()-4)+"-camino-B.txt";
		destiny = new File(name);
		printResults(destiny,ffb,cfb,1);
		
		planificacionTiempos(1,orientacionInicialB,orientacionFinalB);
		imprimirPlanificacionTiempos(new File(file.getAbsolutePath().substring(0, file.getAbsolutePath().length()-4)+"-tiempos-A-B.txt"));
		/*
		for (int k = 0; k < celdas[0].length; k++) {
			for (int k2 = 0; k2 < celdas[0][0].length; k2++) {
				Celda c = obtenerCeldaTiempo(k, k2, 0);
				int costo = (int)c.getCostoTiempo();
				if(c.getEstado()==Celda.PARED)
					System.out.print("oo");
				else if(costo>=0 && costo < 10)
					System.out.print("0"+costo);
				else
					System.out.print(costo);
				System.out.print(" ");
			}
			System.out.println();
		}*/
	}
	
	public void fixPoints(int robot){
		int pos = 0;
		for (int i = 1; i < esquinas[robot].size()-1; i++) {
			Celda es1 = esquinas[robot].get(i-1);
			Celda es2 = esquinas[robot].get(i);
			int p1 = -1;
			int p2 = -1;
			for (pos=0; pos < lista[robot].size(); pos++) {
				
				if(lista[robot].get(pos).equals(es1)){
					p1 = pos-1;
				}
				if(lista[robot].get(pos).equals(es2)){
					p2=pos+1;
					break;
				}
			}
			System.out.println(p1+"¡¡"+p2);
			if(p1>=0 && p2>=0 && lista[robot].get(p1).getOrientacion() == lista[robot].get(p2).getOrientacion()){
				for (int j = p1+2; j < p2-1; j++) {
					lista[robot].get(j).setEstado(Celda.NO_VIABLE);
				}
			}
			
			
		}
	}
	
	public void findPoints(String fileName,int robot)throws Exception{
		Point inicial;
		char orientacionI;
		char orientacionF;
		if(robot == 0){
			inicial = inicialA;
			orientacionI = orientacionInicialA;
			orientacionF = orientacionFinalA;
		}else{
			inicial = inicialB;
			orientacionI = orientacionInicialB;
			orientacionF = orientacionFinalB;
		}
		PrintWriter pw = new PrintWriter(new File(fileName));
		int dVisita = 100;
		int dMin = 60;
		pw.println(dVisita +" "+ dMin);
		//pw.println(inicial.getPosX() +" "+ inicial.getPosY());
		//pw.println(fin.getPosX() +" "+ fin.getPosY()+ " 90");
		/*for (Celda celda : esquinas[robot]) {
			System.out.println("Esquina=>"+celda.getFila()+"-"+celda.getColumna());
		*/
		pw.println(esquinas[robot].size());
		for (Celda esquina : esquinas[robot]) {
			
			int fila = esquina.getFila();
			int columna = esquina.getColumna();
			double x = ((columna-1)*TAMANIO_CELDA + TAMANIO_CELDA/2 - inicial.getPosX());
			double y = ((celdas[robot].length-fila-2)*TAMANIO_CELDA + TAMANIO_CELDA/2-inicial.getPosY());
			if(celdas[robot][fila+1][columna+1][0].getEstado() == Celda.PARED){
				x-=TAMANIO_CELDA/2;
				y+=TAMANIO_CELDA/2;
			}else if(celdas[robot][fila+1][columna-1][0].getEstado() == Celda.PARED){
				x+=TAMANIO_CELDA/2;
				y+=TAMANIO_CELDA/2;
			}else if(celdas[robot][fila-1][columna-1][0].getEstado() == Celda.PARED){
				x+=TAMANIO_CELDA/2;
				y-=TAMANIO_CELDA/2;
			}else if(celdas[robot][fila-1][columna+1][0].getEstado() == Celda.PARED){
				x-=TAMANIO_CELDA/2;
				y-=TAMANIO_CELDA/2;
			}
			int otro = (robot+1)%2;
			int corrimiento=0;
			if(obtenerCeldaTiempo(fila-1, columna, otro).getCostoTiempo()>= 0){
				boolean wall = false;
				for (int i = columna-1; i < columna+1; i++) {
					wall = wall || celdas[robot][fila+1][i][0].getEstado()==Celda.PARED;
				}
				if(!wall){
					y-=corrimiento;
				}
			}else if(obtenerCeldaTiempo(fila+1, columna, otro).getCostoTiempo()>= 0){
				boolean wall = false;
				for (int i = columna-1; i < columna+1; i++) {
					wall = wall || celdas[robot][fila-1][i][0].getEstado()==Celda.PARED;
				}
				if(!wall){
					y+=corrimiento;
				}
			}else if(obtenerCeldaTiempo(fila, columna-1, otro).getCostoTiempo()>= 0){
				boolean wall = false;
				for (int i = fila-1; i < fila+1; i++) {
					wall = wall || celdas[robot][i][columna+1][0].getEstado()==Celda.PARED;
				}
				if(!wall){
					x+=corrimiento;
				}
			}else if(obtenerCeldaTiempo(fila, columna+1, otro).getCostoTiempo()>= 0){
				boolean wall = false;
				for (int i = fila-1; i < fila+1; i++) {
					wall = wall || celdas[robot][i][columna-1][0].getEstado()==Celda.PARED;
				}
				if(!wall){
					x-=corrimiento;
				}
			}
			//referenciar las coordenadas de acuerdo a la orientacion inicial del robot
			if(orientacionI == 'N'){
				double tmp = x;
				x=y;
				y=-tmp;
			}else if(orientacionI == 'S'){
				double tmp = x;
				x=-y;
				y=tmp;
			}else if(orientacionI == 'W'){
				x = -x;
				y= -y;
			}
			pw.println( (int)x+ " "+(int)y);
		}
		int ang = 0;
		if(orientacionI == 'N'){
			ang = 90;
		}else if(orientacionI == 'W'){
			ang = 180;
		}else if(orientacionI == 'S'){
			ang = 270;
		}
		
		int ang2 = 0;
		if(orientacionF == 'N'){
			ang2 = 90;
		}else if(orientacionF== 'W'){
			ang2 = 180;
		}else if(orientacionF == 'S'){
			ang2 = 270;
		}
		pw.println((ang2-ang+360)%360);
		pw.close();
		
		
	}
	
	private void findPath(int fi,int ci,int ff, int cf, char orIn, int robot){
		lista[robot] = new ArrayList();
		esquinas[robot] = new ArrayList<Celda>();
		Celda c1 = celdas[robot][fi][ci][dirToNum(orIn)];
		if(c1.getCosto()<0){
			return;
		}
		lista[robot].add(c1);
		char lastDir = orIn;
		while(c1.getFila() != ff || c1.getColumna() != cf){
			char actualDir='L';
			Celda ca = c1;
			Celda[][] vecinos = new Celda[4][4];
			vecinos[1] =celdas[robot][c1.getFila()-1][c1.getColumna()]; 
			vecinos[2] =celdas[robot][c1.getFila()+1][c1.getColumna()]; 
			vecinos[0] =celdas[robot][c1.getFila()][c1.getColumna()+1];
			vecinos[3] =celdas[robot][c1.getFila()][c1.getColumna()-1];
			c1 = ca;
			for (int i = 0; i < vecinos.length; i++) {
				int m = (i==dirToNum(ca.getOrientacion())&&lista[robot].size()==1)?0:0;
				if((c1.getEstado()==Celda.PARED || ((c1.getCosto()>vecinos[i][i].getCosto()+m || (c1.getCosto()==vecinos[i][i].getCosto() && i==dirToNum(ca.getOrientacion()))) && vecinos[i][i].getEstado()!=Celda.PARED))){
						if(vecinos[i][i].getEstado()!=Celda.NO_VIABLE){
							c1 = vecinos[i][i];
						}
					}
				//}
			}
			actualDir = c1.getOrientacion();
			if(lastDir != actualDir){
				esquinas[robot].add(ca);
				lastDir=actualDir;
				//System.out.println(ca.getFila()+ ","+ca.getColumna()+" added");
			}
			if(lista[robot].size()<30)
			//System.out.println(c1.getFila()+ ","+c1.getColumna()+" checked");
			lista[robot].add(c1);
		}
		esquinas[robot].add(c1);
	}
	
	private void generateMatrix(int ff, int cf,int robot, char orIn){
		Queue<Celda> ss = new LinkedList<Celda>();
		
		//Stack<Celda> ss = new Stack<Celda>();
		for (int i = 0; i < 4; i++) {
			if(i==dirToNum(orIn)){
				celdas[robot][ff][cf][i].setCosto(0);
			}else{				
				celdas[robot][ff][cf][i].setCosto(0);
			}
			ss.add(celdas[robot][ff][cf][i]);
		}
		while(!ss.isEmpty()){
			Celda c = ss.poll();
			if(c.getEstado()== Celda.PARED || c.getEstado() == Celda.NO_VIABLE){
				ss.remove(c);
				continue;
			}
			
			
			Celda[][] vecinos = new Celda[4][4];
			vecinos[1] =celdas[robot][c.getFila()+1][c.getColumna()]; //Norte
			vecinos[2] =celdas[robot][c.getFila()-1][c.getColumna()]; //Sur
			vecinos[0] =celdas[robot][c.getFila()][c.getColumna()-1]; //Este
			vecinos[3] =celdas[robot][c.getFila()][c.getColumna()+1]; //Oeste
			if(vecinos[0][0].getEstado()*vecinos[1][0].getEstado()*vecinos[2][0].getEstado()*vecinos[3][0].getEstado()==0){
				c.setCosto(c.getCosto()+0.01);
			}
			int or = dirToNum(c.getOrientacion());
			if(vecinos[or][or].getCosto()==-1 ||vecinos[or][or].getCosto() > c.getCosto()+1){
				for (int i = 0; i < vecinos.length; i++) {
					if(i==or){
						vecinos[or][or].setCosto(c.getCosto()+1);
						ss.offer(vecinos[or][i]);
					}else if(vecinos[or][i].getCosto()==-1 ||vecinos[or][i].getCosto()>c.getCosto()+2){
						vecinos[or][i].setCosto(c.getCosto()+2);
						ss.offer(vecinos[or][i]);
					}
				}
			}
			ss.remove(c);
			
		}
	}
	
	public void printResults(File destiny,int ff,int cf,int robot) throws Exception{
		NumberFormat nf = NumberFormat.getInstance();
		nf.setMaximumFractionDigits(0);
		nf.setMinimumFractionDigits(0);
		nf.setMaximumIntegerDigits(2);
		nf.setMinimumIntegerDigits(2);
		/*
		for (int i = 0; i < celdas[robot].length; i++) {
			for (int j = 0; j < celdas[robot][0].length; j++) {
				if(obtenerCelda(i,j,robot).getEstado()==Celda.PARED){
					System.out.print(" ooo");
				}else{
					System.out.print(" "+(char)('a'+robot)+nf.format(celdas[robot][i][j][0].getCosto()));
				}
			}
			System.out.println();
		}*/
		
		
		
		PrintWriter pw = new PrintWriter(destiny);
		pw.println("QI "+ inicialA.getPosX()+" "+inicialA.getPosY());
		pw.println("QF "+ finA.getPosX()+" "+finA.getPosY());
		pw.println(celdas.length+" "+celdas[0].length);
		pw.println();
		pw.println("----------Costo movimiento----------");
		pw.println();
		for (int i = 0; i < celdas[robot].length; i++) {
			String s = "";
			for (int j = 0; j < celdas[robot][0].length; j++) {
				if(obtenerCelda(i,j,robot).getEstado()==Celda.PARED){
					s+="oo ";
				}else{
					int l = -1;
					for (int j2 = 0; j2 < lista[robot].size(); j2++) {
						if(lista[robot].get(j2).getFila()==i && lista[robot].get(j2).getColumna()==j){
							l=j2;
						}
					}
					if(l!=-1){
						s+=nf.format(lista[robot].size()-l-1)+" ";
						//s+=lista.get(l).getOrientacion()+""+lista.get(l).getOrientacion()+" ";
					}else if(lista[robot].size()==0 && i == ff && j == cf){
						s+="-1 ";
					}else{
						s+="-- ";
					}
				}
				
					
				
			}
			pw.println(s);
		}
		
		pw.close();
	}
	
	public static void main(String[] args) {
		try{
			Planificacion p = new Planificacion();
			
			/*p.loadMap(new File("problema2-mundo1-7x17.txt"));
			p.findPoints("problema2-mundo1-7x17-puntos.txt");
			
			p.loadMap(new File("problema2-mundo2-7x17.txt"));
			p.findPoints("problema2-mundo2-7x17-puntos.txt");
			
			p.loadMap(new File("problema2-mundo3-7x17.txt"));
			p.findPoints("problema2-mundo3-7x17-puntos.txt");
			
			p.loadMap(new File("problema2-mundo4-7x17.txt"));
			p.findPoints("problema2-mundo4-7x17-puntos.txt");
			p.loadMap(new File("problema2-mundo5-7x17.txt"));
			p.findPoints("problema2-mundo5-7x17-puntos.txt");
			*/
			//p.loadMap(new File("./problema3-mundo1/problema3-mundo1-7x17.txt"));
			//p.loadMap(new File("./problema3-mundo2/problema3-mundo2-7x17.txt"));
			p.loadMap(new File("./problema3-mundo3/problema3-mundo3-7x17.txt"));
			//p.loadMap(new File("./problema3-mundo4/problema3-mundo4-7x17.txt"));
			//p.loadMap(new File("./problema3-mundo5/problema3-mundo5-7x17.txt"));
			//p.loadMap(new File("./problema3-mundo6/problema3-mundo6-7x17.txt"));
			//p.findPoints("problema3-mundo1/problema3-mundo1-7x17-puntos.txt",0);
		}catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private char numToDir(int num){
		if(num==0){
			return 'E';
		}else if(num==1){
			return 'N';
		}else if(num==2){
			return 'S';
		}else{
			return 'W';
		}
		
	}
	
	private int dirToNum(char dir){
		if(dir=='E'){
			return 0;
		}else if(dir=='N'){
			return 1;
		}else if(dir=='S'){
			return 2;
		}else{
			return 3;
		}
	}
	
	private Celda obtenerCelda(int f, int c,int robot){
		Celda celda = celdas[robot][f][c][0];
		for (int i = 1; i < 4; i++) {
			Celda c2 = celdas[robot][f][c][i];
			if(c2.getCosto()<celda.getCosto()){
				celda=c2;
			}
		}
		return celda;
	}
	
	private Celda obtenerCeldaTiempo(int f, int c, int robot){
		Celda celda = celdas[robot][f][c][0];
		for (int i = 1; i < 4; i++) {
			Celda c2 = celdas[robot][f][c][i];
			if(c2.getCostoTiempo()>celda.getCostoTiempo()){
				celda=c2;
			}
		}
		return celda;
	}
	
	public void planificacionTiempos(int robot, int orIn, int orFin){
		Celda celda = lista[robot].get(0);
		Celda ant;
		if(celda.getOrientacion()==orIn ){
			celda.setCostoTiempo(0);
		}else{
			celda.setCostoTiempo(1);
		}
		for (int i = 1; i < lista[robot].size()-1; i++) {
			celda = lista[robot].get(i);
			ant = lista[robot].get(i-1);
			if(ant.getOrientacion()==celda.getOrientacion()){
				celda.setCostoTiempo(ant.getCostoTiempo()+1);
			}else{
				celda.setCostoTiempo(ant.getCostoTiempo()+2);
			}
		}
		ant = lista[robot].get(lista[robot].size()-2);
		celda = lista[robot].get(lista[robot].size()-1);
		if(ant.getOrientacion()== orFin){
			celda.setCostoTiempo(ant.getCostoTiempo()+1);
		}else{
			celda.setCostoTiempo(ant.getCostoTiempo()+2);
		}
	}
	
	public void imprimirPlanificacionTiempos(File f){
		try{
			PrintWriter pw = new PrintWriter(f);
			
			for (int k = 0; k < celdas[0].length; k++) {
				String print = "";
				for (int k2 = 0; k2 < celdas[0][0].length; k2++) {
					Celda ca = obtenerCeldaTiempo(k, k2, 0);
					Celda cb = obtenerCeldaTiempo(k, k2, 1);
					int coa = ca.getCostoTiempo();
					int cob = cb.getCostoTiempo();
					if(ca.getEstado()==Celda.PARED){
						print+="ooo";
					}else if(coa == -1 && cob == -1){
						print+="---";
					}else if(coa != -1 && cob != -1){
						print+="a-b";
					}else if(coa != -1){
						if(coa<10){
							print+="a0"+coa;
						}else{
							print+="a"+coa;
						}
					}else{
						if(cob<10){
							print+="b0"+cob;
						}else{
							print+="b"+cob;
						}
					}
					print+=" ";
				}
				pw.println(print);
			}
			pw.close();
		}catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public void fixEncounters(){
		
		int encounters = 0;
		ArrayList<Celda> pts = new ArrayList<Celda>();
		//System.out.println("Tamanio!: "+lista[1].size());
		for (Celda celda : lista[1]) {
			int f = celda.getFila();
			int c = celda.getColumna();
			int costo = obtenerCeldaTiempo(f, c, 0).getCostoTiempo();
			//System.out.println(f+","+c+" candidato "+costo);
			if(costo >=0){
				encounters++;
				pts.add(celda);
			}else{
				if(pts.size()>1){
					int f1 = pts.get(pts.size()/2).getFila();
					int c1 = pts.get(pts.size()/2).getColumna();
					celdas[1][f1][c1][0].setEstado(Celda.NO_VIABLE);
					celdas[1][f1][c1][1].setEstado(Celda.NO_VIABLE);
					celdas[1][f1][c1][2].setEstado(Celda.NO_VIABLE);
					celdas[1][f1][c1][3].setEstado(Celda.NO_VIABLE);
				}
				pts.clear();
				encounters=0;
			}
		}
	}
	
}
